package coding_round_1

//self.ans = 1
//def depth(node):
//# 访问到空节点了，返回0
//if not node:
//return 0
//# 左儿子为根的子树的深度
//L = depth(node.left)
//# 右儿子为根的子树的深度
//R = depth(node.right)
//# 计算d_node即L+R+1 并更新ans
//self.ans = max(self.ans, L + R + 1)
//# 返回该节点为根的子树的深度
//return max(L, R) + 1
//
//depth(root)
//return self.ans - 1

// 求一颗二叉树的直径，有可能穿过根节点，有可能不穿过
func diameterOfBinaryTree(root *TreeNode) int {
	var ans int
	var recursion = func(node *TreeNode) int {
		return 0
	}
	recursion = func(node *TreeNode) int {
		if node == nil {
			return 0
		}
		L := recursion(node.Left)
		R := recursion(node.Right)
		ans = max(ans, L+R+1)
		return max(L, R) + 1
	}
	recursion(root)
	return ans - 1
}
